package com.algorithm.pack;

public class CompletePack {

    public static int[][] completePack(int[] weight,int[] value,int volume){
        int N = weight.length;//物品数

        //F[i][v] 表示只使用前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值
        int F[][] = new int[N+1][volume+1];

        for(int i=1;i<=N;i++){
            for(int w = weight[i-1];w<=volume;w++){
                //F[i-1][w]未选第i种物品的子结果
                //F[i][w-weight[i-1]]+value[i-1]加选一件第i种产品的子结果
                F[i][w] = Math.max(F[i-1][w],F[i][w-weight[i-1]]+value[i-1]);
            }
        }

        return F;
    }

    public static int[] completePack_space(int[] weight,int[] value,int volume){
        int N = weight.length;

        int F[] = new int[volume+1];

        for(int i=1;i<=N;i++){
            for(int w=weight[i-1];w<=volume;w++){
                F[w] = Math.max(F[w],F[w-weight[i-1]]+value[i-1]);
            }
        }

        return F;
    }

    public static int completePack_recursive(int N,int[] weight,int[] value,int volume){
        if(N==0 || volume==0){
            return 0;
        }

        int i = N-1;
        if(weight[i] > volume){
            return completePack_recursive(N-1,weight,value,volume);
        }else{
            int value1 = completePack_recursive(N-1,weight,value,volume);
            int value2 = value[i] + completePack_recursive(N,weight,value,volume-weight[i]);
            return Math.max(value1,value2);
        }
    }
}
